#include <stdio.h>
#include "type.h"
#include "alloc.h"
#include "uart.h"


//----------------------------------------------------------------
#define MY_MEM_SIZE	3000
static u08	g_user_mem[MY_MEM_SIZE];
static u08*	g_heap_start;
//----------------------------------------------------------------

int user_malloc_init(void)
{
	u16 i;
	st_mem_head* head;
	int r_size = MY_MEM_SIZE - (sizeof(st_mem_head));

	for(i = 0;i<MY_MEM_SIZE;i++)
		g_user_mem[MY_MEM_SIZE] = 0x00;

	if(r_size<0)
		return 1;
	head = (st_mem_head*) (&g_user_mem[0]);
	head->rlink = NULL;
	head->tag_size = r_size <<1;
	g_heap_start = (void*)&g_user_mem[0];
	return 0;
}


void* get_best_position(u16 size)
{
	void* temp = NULL;
	st_mem_head* head = (st_mem_head*)g_heap_start;
	s16 minsize = -1;
	do
	{
		if(head->tag_size %2 == 0)
		{
			if(minsize > (head->tag_size>>1 )&&(head->tag_size>>1>=size) )
			{
				temp = head;
				minsize = head->tag_size>>1;
			}
		}
		head = head->rlink;
	}
	while(head!=NULL);
	return temp;
}


u08* user_malloc_alloc(u16 size)
{
	st_mem_head* o_head = get_best_position(size);
	st_mem_head* n_head = NULL;


	u16 o_size;
	int n_size;

	if(o_head==NULL)
		return NULL;

	o_size = o_head->tag_size>>1;
	o_head ->tag_size +=1;

	n_size = o_size -size - sizeof(st_mem_head);
	if(n_size > 0 )
	{
		o_head->tag_size = (size<<1)+1;
		n_head = (st_mem_head*)((u08*)o_head+size+sizeof(st_mem_head)) ;
		n_head->rlink = o_head->rlink;
		o_head->rlink = n_head;
		n_head->tag_size = n_size<<1;

	}

	return (u08*)o_head + sizeof(st_mem_head);
}

st_mem_head* get_left_head(void* addr)
{
	void* retv = NULL;
	st_mem_head* begin = (st_mem_head*)g_heap_start;
	u08* tmpaddr = (u08*)addr;
	tmpaddr -= sizeof(st_mem_head);

	while(begin!=(st_mem_head*)tmpaddr)
	{
		retv = begin;
		begin = begin->rlink;
	}
	return retv;
}

void user_malloc_free(void* addr)
{


	st_mem_head* f_head = (st_mem_head*)((u08*)addr - sizeof(st_mem_head));
	st_mem_head* l_head = get_left_head(addr);
	st_mem_head* r_head = f_head->rlink;
	int n_size = 0;
	unsigned char situation = 0;
	if( l_head==NULL|| (l_head->tag_size&1)==1)
	{
		situation|=2;
	}
	if( r_head==NULL|| (r_head->tag_size&1)==1)
	{
		situation|=1;
	}
	//printf("Situation is %d\n",situation);
	switch(situation)
	{
		case 0:
			//Both left and right are not used! Merge all!;
			n_size = (f_head->tag_size>>1) + (l_head->tag_size>>1) + (r_head->tag_size>>1)+ 2*sizeof(st_mem_head);
			l_head->tag_size = n_size<<1;
			l_head->rlink = r_head->rlink;
			break;

		case 1:
			//Left is not used!Merge Left!;
			n_size = (f_head->tag_size>>1) + (l_head->tag_size>>1) + sizeof(st_mem_head);
			l_head->tag_size = n_size<<1;
			l_head->rlink = f_head->rlink;
			break;

		case 2:
			//Right is not used! Merge Right;
			n_size = (f_head->tag_size>>1)+(r_head->tag_size>>1)+sizeof(st_mem_head);
			f_head->tag_size = n_size<<1;
			f_head->rlink = r_head->rlink;
			break;

		case 3:
			//None Merge!
			f_head->tag_size -= 1;
			break;
		default:
			//No this situation except!
			break;
	}
}

void debug_heap(void)
{
	st_mem_head* head = (st_mem_head*)g_heap_start;
	F(("\nheap\r\n"));
	while(head!=NULL)
	{
		F(("%x-",(unsigned int)head));
		F(("%x-",(unsigned int)((u08*)head+(head->tag_size>>1)+sizeof(st_mem_head))));
		F(("%x-%x\r\n",(head->tag_size>>1),(head->tag_size&1)));
		head = head->rlink;
	}
//	F(("d_heap_end:-------------\r\n"));
}
/*
   void debug_heap_extern(void)
   {

   st_mem_head* head = (st_mem_head*)g_heap_start;
   printf("\ndebug_heap_start:-------------\r\n");
   while(head!=NULL)
   {
   printf("start = %x ",(unsigned int)head);
   printf("end = %x ",(unsigned int)((u08*)head+(head->tag_size>>1)+sizeof(st_mem_head)));
   printf("size = %d isused = %d\n",(head->tag_size>>1),(head->tag_size&1));
   head = head->rlink;
   }
   printf("debug_heap_end:-------------\r\n");

   }
   */
